We examine the nature of the progenitor of the giant stellar stream in M31 using as constraints new radial velocity measurements of stream red giant stars (presented in the companion paper by Guhathakurta et al. 2005, astro-ph/0406145) along with other M31 data sets available in the literature. We find that the observations are best fit by orbits that are highly eccentric and close to edge-on, with apo- to peri-center ratios of order 25 - 30, and with apocenters at or only slightly beyond the southern edge of the current data. Among these orbits, we are able to find a few that plausibly connect the stream with the northern spur or with the low-surface-brightness feature of similar high metallicity as the stream (originally reported by Ferguson et al. 2002) to the east of M31's center. In the latter case, if the connection is real, then the eastern debris should lie well in front of M31 near the apocenter of the orbit. Both the width of the debris and velocity dispersion measurements imply a rough lower limit on the mass of the progenitor of 10^8 M_sun. We use this limit and our orbits to discuss which of M31's satellites could be plausibly associated with the stream. In addition, we predict that the width of the stream should increase beyond the southern edge of the current data around the apocenter of the orbit and that the line-of-sight velocity dispersion should exhibit significant variations along the stream.